#include <stdio.h>
#include <stdlib.h>

#define MAX     21

typedef struct my_heap_s {
        int     data[MAX];
        int     n;
} my_heap_t;

void swap(int *a, int *b)
{
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
}

void shiftup(my_heap_t *heap)
{
        int i;
        int t;
        for (i = heap->n; i > 0;) {
                t = i >> 1;
                if (t > 0 && heap->data[t] > heap->data[i]) {
                        swap(&heap->data[t], &heap->data[i]);
                }

                i = t;
        }
}

void insert_heap(my_heap_t *heap, int value)
{
        if (NULL == heap) {
                printf("Null heap.\n");
                return;
        }
        if (heap->n >= (MAX - 1)) {
                printf("Full heap.\n");
                return;
        }

        ++heap->n;
        heap->data[heap->n] = value;
        shiftup(heap);
}

void shiftdown(my_heap_t *heap)
{
        int s, p1, p2, n, min;
        
        if (heap->n == 0)
                return;

        s = 1;
        n = heap->n;
        while(1) {
                p1 =  s << 1;
                p2 = p1 + 1;

                if (p1 > n && p2 > n)
                        return;
                
                if (p1 > n)
                        min = p2;
                else if (p2 > n)
                        min = p1;
                else {
                        if (heap->data[p1] < heap->data[p2])
                                min = p1;
                        else
                                min = p2;
                }
                if (heap->data[s] > heap->data[min]) {
                        swap(&(heap->data[s]), &(heap->data[min]));
                        s = min;
                }
                else
                        return;
        }
}

int delete_heap(my_heap_t *heap)
{
        int del_item;

        if (NULL == heap) {
                printf("Null heap.\n");
                return -1;
        }
        if (heap->n == 0) {
                printf("Empty heap.\n");
                return -1;
        }

        del_item = heap->data[1];
        heap->data[1] = heap->data[heap->n];
        --heap->n;
        shiftdown(heap);

        return del_item;
}

int main()
{
        my_heap_t heap = {0};
        int test[] = {2,3,1,5,9,7,3,6};

        int i = 0;
        for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
                insert_heap(&heap, test[i]);
        }
        while (heap.n > 0) {
                printf("Delete %d from heap.\n", delete_heap(&heap));
        }

        return 0;
}
